package 快速排序;

import com.sun.xml.internal.bind.v2.model.annotation.Quick;

import java.util.Scanner;

/**
 * *给定你一个长度为 n 的整数数列。
 *
 * 请你使用快速排序对这个数列按照从小到大进行排序。
 *
 * 并将排好序的数列按顺序输出。
 *
 * 输入格式
 * 输入共两行，第一行包含整数 n。
 *
 * 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
 *
 * 输出格式
 * 输出共一行，包含 n 个整数，表示排好序的数列。
 *
 * 数据范围
 * 1≤n≤100000
 * 输入样例
 * 5
 * 3 1 2 4 5
 * 输出样例
 * 1 2 3 4 5
 */
public class Solution {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i =0;i<n;i++){
            nums[i] = sc.nextInt();
        }
        int[] ans = quickSort(0, n - 1, nums);

    }

    /**
     * @param left
     * @param right 数组长度
     * @param nums 排序数组
     *    快排需要提供privort，两层循环遍历，从右至左，从左至右
     */
    public static int[] quickSort(int left ,int right ,int[] nums){
        //每次要以privot分割数组为两边
        //左右两边分别进行一次排序
        if (left>=right){
            return nums;
        }
        //哨兵节点
        int temp = nums[left];

        // 左右
        int i = left;
        int j = right;
        // 左右指针重合，代表本次没有需要进行交换，停止
        while(i<j){
            // 在右边找到第一个小于哨兵的元素
            while(nums[j]>=temp&&i<j){
                j--;
            }
            // 在左边找到第一个大于哨兵的元素
            while(nums[i]<=temp&&i<j){
                i++;
            }
            // 需要交换的两个元素不重合，将其进行交换
            if (i<j){
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
         // 找到合适的位置存放哨兵节点，i始终满足要比temp要小，因为j先走，会收敛到第一个比temp小的元素，i在走的时候始终在j左
        // 直至走向同一节点，导致结束
        nums[left] = nums[i];
        nums[i] = temp;

        // 排完一次递归排左右
        quickSort(left,i-1,nums);
        quickSort(i+1,right,nums);
        return nums;
    }

    public void quickSortSimple(int l,int r,int[] nums){
        if (l>=r){
            return ;
        }
        int temp = nums[l+r>>1],i=l-1,j=r+1;
        //这样写的好处是一开始就可以处理哨兵位置
        while(i<j){
            while(nums[--j]>temp) {
                ;
            }
            while(nums[++i]<temp) {
                ;
            }
            if(i<j) {
                swap(i,j,nums);
            }
        }
        quickSortSimple(l,j,nums);
        quickSortSimple(j+1,r,nums);
    }

    public void swap(int i,int j,int[] nums){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }


}
